# 希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，
# 重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。
# 最后整个表就只有一列了


def shell_sort(alist):
    n = len(alist)
    # 初始步长
    gap = n // 2
    while gap > 0:
        # 按步长进行插入排序
        for i in range(gap, n):
            j = i
            # 插入排序
            while j >= gap and alist[j-gap] > alist[j]:
                alist[j-gap], alist[j] = alist[j], alist[j-gap]
                j -= gap
        # 得到新的步长
        gap = gap // 2


alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
shell_sort(alist)
print(alist)


